package cn.edu.ncepu;

public class PrimChecker {

    /**
     * 对应Python的check函数，验证a和n的关系
     * @param a 测试底数
     * @param n 待验证数
     * @return 验证结果
     */
    private static boolean check(long a, long n) {
        long x = n;
        long p = n + 1;

        // 当x是偶数时循环
        while ((x & 1) == 0) {
            x >>= 1; // 右移一位，等价于除以2
            // 计算(a^x + 1) % p，使用快速幂避免溢出
            if ((powMod(a, x, p) + 1) % p == 0) {
                return true;
            }
        }
        // 验证(a^x - 1) % p == 0
        return (powMod(a, x, p) - 1) % p == 0;
    }

    /**
     * 快速幂实现：(base^exponent) % mod，避免大数溢出
     * @param base 底数
     * @param exponent 指数
     * @param mod 模数
     * @return 计算结果
     */
    private static long powMod(long base, long exponent, long mod) {
        long result = 1;
        base = base % mod; // 先取模，减少计算量
        while (exponent > 0) {
            // 如果指数是奇数，结果乘以当前底数
            if ((exponent & 1) == 1) {
                result = (result * base) % mod;
            }
            // 指数右移一位（除以2），底数平方后取模
            exponent >>= 1;
            base = (base * base) % mod;
        }
        return result;
    }

    /**
     * 对应Python的is_prim函数，判断是否为质数
     * @param n 待判断的数
     * @return 是否为质数
     */
    private static boolean isPrim(long n) {
        // 处理小数值
        if (n <= 4) {
            return n == 2 || n == 3;
        }
        // 偶数直接返回false
        if ((n & 1) == 0) {
            return false;
        }

        // 测试底数数组，与Python版本一致
        long[] testBases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (long a : testBases) {
            if (!check(a, n - 1)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isPrim(10000) + " " + 10000);
        System.out.println(isPrim(911) + " " + 911);
        System.out.println(isPrim(561) + " " + 561);
        System.out.println(isPrim(341) + " " + 341);
    }
}